package LeetCode.month02.day33;

import java.util.Arrays;

public class No2968 {
    public int maxFrequencyScore(int[] nums, long k) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] arr = new long[n+1];
        arr[0]=0;
        for (int i = 1; i <=n ; i++) {
            arr[i] = arr[i-1]+nums[i-1];
        }
        int ans = 0;
        int left = 0;
        for (int i = 0; i < n; i++) {
            while(distanceSum(arr,nums,left,(left+i)/2,i)>k){
                left++;
            }
            ans = Math.max(ans,i-left+1);
        }
        return ans;
    }
    long distanceSum(long[] s, int[] nums, int l, int i, int r) {
        long left = (long) nums[i] * (i - l) - (s[i] - s[l]);
        long right = s[r + 1] - s[i + 1] - (long) nums[i] * (r - i);
        return left + right;
    }
}
